﻿namespace AdvancedTraining.Lesson37;

/// <summary>
/// 来自网易的项目安排问题
/// </summary>
/// <remarks>
/// 刚入职网易互娱，新人mini项目便如火如荼的开展起来。为了更好的项目协作与管理，
/// 小易决定将学到的甘特图知识用于mini项目时间预估。小易先把项目中每一项工作以任务的形式列举出来，
/// 每项任务有一个预计花费时间与前置任务表，必须完成了该任务的前置任务才能着手去做该任务。
/// 作为经验PM，小易把任务划分得井井有条，保证没有前置任务或者前置任务全数完成的任务，都可以同时进行。
/// 小易给出了这样一个任务表，请作为程序的你计算需要至少多长时间才能完成所有任务。
///
/// 输入格式：
/// 第一行为一个正整数T，表示数据组数。
/// 对于接下来每组数据，第一行为一个正整数N，表示一共有N项任务。
/// 接下来N行，每行先有两个整数Di和Ki，表示完成第i个任务的预计花费时间为Di天，该任务有Ki个前置任务。
/// 之后为Ki个整数Mj，表示第Mj个任务是第i个任务的前置任务。
///
/// 数据范围：1<=T<=3, 1<=N, Mj<=100000, 0<=Di<=1000, 0<=sum(Ki)<=N*2
///
/// 算法思路：
/// 使用拓扑排序的思想，从没有前置任务的任务开始处理。
/// 使用队列记录当前可以执行的任务，动态更新每个任务的最早完成时间。
/// 时间复杂度：O(N + E)，其中E是前置任务关系的总数
/// 空间复杂度：O(N + E)
/// </remarks>
public class ArrangeProject
{
    /// <summary>
    /// 计算完成所有任务需要的最少天数
    /// </summary>
    /// <param name="numbers">邻接表，numbers[i]表示任务i的后置任务列表</param>
    /// <param name="days">每个任务需要的天数</param>
    /// <param name="headCount">每个任务的前置任务数量</param>
    /// <returns>完成所有任务需要的最少天数</returns>
    public static int DayCount(List<int>[] numbers, int[] days, int[] headCount)
    {
        var head = CountHead(headCount);
        var maxDay = 0;
        var countDay = new int[days.Length];
        while (head.Count > 0)
        {
            var cur = head.First();
            head.RemoveFirst();
            countDay[cur] += days[cur];
            for (var j = 0; j < numbers[cur].Count; j++)
            {
                headCount[numbers[cur][j]]--;
                if (headCount[numbers[cur][j]] == 0) head.AddLast(numbers[cur][j]);
                countDay[numbers[cur][j]] = Math.Max(countDay[numbers[cur][j]], countDay[cur]);
            }
        }

        foreach (var item in countDay)
            maxDay = Math.Max(maxDay, item);

        return maxDay;
    }

    /// <summary>
    /// 找出所有没有前置任务的任务
    /// </summary>
    /// <param name="headCount">每个任务的前置任务数量</param>
    /// <returns>没有前置任务的任务队列</returns>
    private static LinkedList<int> CountHead(int[] headCount)
    {
        var queue = new LinkedList<int>();
        for (var i = 0; i < headCount.Length; i++)
            if (headCount[i] == 0)
                queue.AddLast(i); // 没有前驱任务
        return queue;
    }

    /// <summary>
    /// 运行测试用例
    /// </summary>
    public static void Run()
    {
        Console.WriteLine("=== ArrangeProject 测试 ===");

        // 测试用例1：简单链式依赖
        // 任务0(2天) -> 任务1(3天) -> 任务2(1天)
        var numbers1 = new List<int>[3];
        for (int i = 0; i < 3; i++) numbers1[i] = new List<int>();
        numbers1[0].Add(1);  // 任务0的后置任务：任务1
        numbers1[1].Add(2);  // 任务1的后置任务：任务2
        var days1 = new int[] { 2, 3, 1 };
        var headCount1 = new int[] { 0, 1, 1 };  // 任务0无前置，任务1有1个前置，任务2有1个前置
        Console.WriteLine($"测试1 - 链式依赖: 期望=6, 实际={DayCount(numbers1, days1, headCount1)}");

        // 测试用例2：并行任务
        // 任务0(2天) 和 任务1(3天) 可以并行，都完成后 任务2(1天) 才能开始
        var numbers2 = new List<int>[3];
        for (int i = 0; i < 3; i++) numbers2[i] = new List<int>();
        numbers2[0].Add(2);
        numbers2[1].Add(2);
        var days2 = new int[] { 2, 3, 1 };
        var headCount2 = new int[] { 0, 0, 2 };  // 任务0和1无前置，任务2有2个前置
        Console.WriteLine($"测试2 - 并行任务: 期望=4, 实际={DayCount(numbers2, days2, headCount2)}");

        // 测试用例3：复杂依赖图
        // 任务0(1天), 任务1(2天) -> 任务3(1天)
        // 任务0(1天) -> 任务2(3天)
        var numbers3 = new List<int>[4];
        for (int i = 0; i < 4; i++) numbers3[i] = new List<int>();
        numbers3[0].Add(2);
        numbers3[0].Add(3);
        numbers3[1].Add(3);
        var days3 = new int[] { 1, 2, 3, 1 };
        var headCount3 = new int[] { 0, 0, 1, 2 };  // 任务0和1无前置，任务2有1个前置，任务3有2个前置
        Console.WriteLine($"测试3 - 复杂依赖: 期望=4, 实际={DayCount(numbers3, days3, headCount3)}");

        // 测试用例4：单任务
        var numbers4 = new List<int>[1];
        numbers4[0] = new List<int>();
        var days4 = new int[] { 5 };
        var headCount4 = new int[] { 0 };
        Console.WriteLine($"测试4 - 单任务: 期望=5, 实际={DayCount(numbers4, days4, headCount4)}");

        // 测试用例5：多个独立任务（完全并行）
        var numbers5 = new List<int>[4];
        for (int i = 0; i < 4; i++) numbers5[i] = new List<int>();
        var days5 = new int[] { 2, 3, 1, 4 };
        var headCount5 = new int[] { 0, 0, 0, 0 };  // 所有任务都没有前置
        Console.WriteLine($"测试5 - 完全并行: 期望=4, 实际={DayCount(numbers5, days5, headCount5)}");

        Console.WriteLine("=== 测试完成 ===");
    }
}